package Array;

/**
 6. Z 字形变换
 *
 * 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
 *
 * 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
 *
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
 *
 * 请你实现这个将字符串进行指定行数变换的函数：
 *
 * 思路： 1、先定义一个二维数组， 大小为 numRows * s.length()， 将字符串先转换为char数组用于遍历
 *       2、遍历char数组，将每个char放入对应的二维数组中，规则如下：
 *          - 1、当行数为1时，直接返回s
 *          - 2、i不变，j+1, 依次放入字符串，直到j == numRows-1
 *              接着i+1,j-1，直到j == 0
 *              如果前两步后数组还未遍历完成，则继续下一轮。
 *      3、将二维数组转换为字符串，返回
 *  实际上，Z字字符串是有规律的，其周期长度为2*numRows-2，
 *      所以我们可以利用周期长度来计算出每个字符应该在二维数组中的位置，没必要进行索引下标的加减，
 *  解题思路如下：
 *      特殊情况处理：
     * 如果 numRows 为 1，直接返回原字符串，因为 Z 字形排列退化为一行。
     * 计算周期：
     * Z 字形排列的周期长度为 2 * numRows - 2。这是因为每一行的字符间隔是固定的。
     * 构建结果字符串：
     * 使用一个 StringBuilder 来构建最终的结果字符串。
     * 遍历每一行，对于每一行，根据周期长度计算出该行的字符位置，并将这些字符添加到 StringBuilder 中。
     * 处理每一行：
     * 第一行和最后一行的字符间隔是固定的，为周期长度。
     * 中间行的字符间隔有两种情况，需要分别处理。
 */
public class L_6 {

    /**
     * 特殊情况处理：
     * 如果 numRows 为 1，直接返回原字符串 s。
     * 计算周期：
     * cycleLen = 2 * numRows - 2，这是 Z 字形排列的周期长度。
     * 构建结果字符串：
     * 使用 StringBuilder 来构建最终的结果字符串 result。
     * 处理每一行：
     * 外层循环遍历每一行 i。
     * 内层循环遍历每个周期 j，计算当前周期内该行的字符位置 j + i。
     * 对于中间行（即 i 不是第一行也不是最后一行），还需要处理周期内的另一个字符位置 j + cycleLen - i。
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if(numRows == 1){
            return s;
        }
        StringBuilder sb =new StringBuilder();
        int n = s.length();
        int cycle = 2 * numRows - 2; // Z 字形排列的周期长度规律
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j+i < n; j += cycle) {
                // 添加当前字符到结果字符串中
                sb.append(s.charAt(j+i));
                // 如果当前行不是第一行也不是最后一行，则添加下一个周期的字符
                if(i!=0 && i!=numRows-1 && j+cycle-i < n){
                    sb.append(s.charAt(j+cycle-i));
                }
            }
        }
        return sb.toString();
    }
}
